Fault simulation is the simulating of a circuit in the presence of faults. Comparing the fault simulation results with those of the fault-free simulation of the same circuit simulated with the same applied test T, the faults detected by T can be determined. One use of fault simulation is to evaluate (grade) a test T which is given by its fault coverage, i.e., which is the ratio of the number of faults detected by T to the total number of simulated faults. Fault simulation can be used with different fault models, such as stuck-at faults, bridging faults, etc.
Fault simulation plays an important role in test generation, by determining the faults accidentally detected by a test vector or test sequence generated for a specific target fault. Then all the detected faults are discarded from the set of simulated faults, and a new target fault is selected from the remaining ones. This avoids the much greater computational effort involved in generating tests by explicitly targeting the accidentally detected faults.
Fault simulation is extensively used in fault diagnosis. One technique for doing so employs precomputed fault dictionaries, where all possible faulty responses are stored for comparison with the actual response of the device under test. Another technique, used as part of post-test diagnosis, first isolates a reduced set of "plausible" faults, and then simulated only these faults to find the one(s) whose response agrees with the actual response.
In Digital Systems Testing and Testable Design, by M. Abramovici, M. A. Breuer, and A. D. Friedman, I.E.E.E. Press, 1994, many efficient software-implemented fault simulation algorithms are discussed. However, complex circuits and long test sequences make fault simulation in software a very time-consuming computational process.
Many different hardware-based approaches have been tried to speed up fault simulation, e.g., methods dividing the set of faults among parallel processors executing the same algorithm, such as described in "Fault Simulation in a Distributed Environment," Proc Design Automation Conf., pp. 686-691, 1988 by P. A. Duba, R. K. Roy, J. A. Abraham, and W. A. Rogers. Unfortunately, these usually result in a speed-up which is a sublinear function of the number of processors. While hardware accelerators specially built for fault simulation do achieve higher performance, such performance comes at a significantly higher cost. Also, a special-purpose processor with a hardwired algorithm is a very inflexible solution. By contrast, a microprogrammed multiprocessor architecture, such as described in "Fault Simulation on a Pipelined Multiprocessor System,"Proc. Intn'l Test Conf., pp. 727-734, 1989, by P.Agrawal, V. D. Agrawal, and K. T.Cheng, offers more flexibility (both logic and fault simulation are implemented on the same machine), but the performance is lower.
Logic emulation systems are increasingly being used for rapid ASIC prototyping, and to support hardware-software co-design and in-system verification. One recent solution, such as described by K.-T.Cheng, S.-Y.Huang, and W.-J. Dai, in "Fault Emulation: A New Approach to Fault Grading,"Proc. Int'l. Conf. on Computer-Aided Design, pp. 681-686, Nov. 1995 and by L. Burgun, F. Reblewski, G. Fenelon, J. Barbier and O. Lepape,"Serial Fault Simulation,"Proc. Design Automation Conf., pp.801-806, 1996, has implemented logic emulators for serial fault simulation, where faults are inserted one-at-a-time in the emulation model of the circuit. The advantage is that fault simulation runs at hardware speed, without having to build any special purpose hardware, and it runs on computing platforms which are becoming widely available.
An important requirement is to have an efficient way of performing fault insertion that avoids full reconfiguration of the emulator for different faults. In the K.-T.Cheng et al. reference, a fault insertion circuit is added to the emulation model, so that faults are inserted without any reconfiguration, just by changing logic values in the model. In the L.Burgun et al. reference, fault insertion takes advantage of the incremental reconfigurability of the target emulator, which allows only a small portion of the model to be reconfigured. Although the K.-T.Cheng et al. reference describes a speed-up technique that allows several faults to be concurrently simulated, the performance of this process, referred to as fault emulation, is still limited by its serial nature.
Thus, it would be highly desirable to overcome the drawbacks mentioned-above by providing a new approach to implement fault simulation on reconfigurable hardware.
Moreover, it would be highly desirable to provide a new approach to implement fault simulation on reconfigurable hardware by implementing a critical path tracing algorithm, an implicit fault processing technique which is described in "Critical Path Tracing: An Alternative to Fault Simulation", IE.E.E. Design & Test of Computers, 1984, by M. Abramovici, P. R. Menon, and D. T. Miller, which is incorporated by reference herein. In critical path tracing, explicit fault enumeration is not required, as most faults are processed implicitly. Instead, for every input vector, critical path tracing first simulates the fault-free circuit, then it determines the detected faults by ascertaining which values are so-called critical. For instance, a line "l" has a critical value v in test t if t detects the fault l s-a-v (stuck-at-v). Such as a line with a critical value in t is said to be critical in t. Finding the lines critical in a test t, enables immediate determination of the faults detected by t. As a starting point, the primary outputs (POs) with binary values are critical in any test. The other critical lines are found by a process starting at the POs and backtracing paths composed of critical lines, called critical paths.
A gate input is sensitive in a test t if complementing its value changes the value of the gate output. If a gate output is critical, then its sensitive inputs are also critical. This provides the basic rule for backtracing critical paths through gates. FIGS. 2(a) and 2(b) illustrate a combinational circuit having the sensitive gate inputs marked by dots and the critical paths indicated by heavy lines.
In the critical path tracing algorithm, when a critical path being traced reaches a fanout stem, stem analysis is performed to determine whether the stem is critical by injecting the appropriate fault at the stem and checking whether its fault effects propagate to any PO. For example, as shown in FIG. 2(a), the stem indicated as "B" is not critical, since the fault effects of B s-a-0 propagate along two paths with different inversion parities that cancel each other at the inputs of the reconvergence gate F (Fault effects are denoted by good.sub.-- value/faulty.sub.-- value). However, as shown in FIG. 2(b), the fault effect propagating along the path (B, BI, D, F) reaches F and therefor B is critical.
In many cases, stem criticality can be determined without stem analysis, based only on criticality of the fanout branches. Such stems can be identified by analyzing the reconvergent structure of the circuit in a preprocessing phase. For example, in FIG. 3(a), both paths that fan out from B and reconverge at E have the same inversion parity. Hence fault effects originating at B can never cancel each other, and, whenever B1 or B2 is critical, the stem can be marked as critical without simulating the stem fault.
FIG. 3(b) illustrates a situation when a critical path is not continuous. Although backtracing stops at gate E, (which has no sensitive inputs), stem B is critical since the effect of B s-a-0 is observed at E. In the case exemplified in FIG. 3(a), whenever gate E is critical and D=E=0, stem analysis must be performed for B, a condition which may be identified during a preprocessing stage. A detailed discussion of conditions for stem analysis is given by P. R. Menon, Y. Levendel, and M. Abramovici in "SCRIPT: A Critical Path Tracing Algorithm for Synchronous Sequential Circuits," IE.E.E. Transactions on Computer-Aided Design, June 1991.